
#include "../spectral_div/spectral_div.h"
#include "../modularity_mat/itemslist.h"
#include "../common/improve_div.h"
#include "../common/mem.h"

int compare_unique(const void* arg1, const void* arg2);

void spectralDiv(sparse_matrix_arr* adj_matrix, elem precision,
				 int* indices, int indices_count, elem* deltaQue,
				 int** g1, int** g2, int* g1Count, int* g2Count)
{
	ModularityMatrix* Bg;
	elem eigenValue;
	Vector* eigenVector;
	/* int n; */
	ItemsList g1List;
	ItemsList g2List;

	itemslist__init(&g1List);
	itemslist__init(&g2List);
	*g1Count = 0;
	*g2Count = 0;
	
	Bg = make_modularity_mat(adj_matrix, indices, indices_count);
	eigenVector = allocate_Vector(indices_count);
	*deltaQue = 0;

	fast_power_method(Bg, precision, eigenVector, &eigenValue);
	
	if (IS_POSITIVE(eigenValue))
	{
		Vector* s_vector;
		Vector* helper;
		int* s;
		int i;
		elem improve_delta;

		helper = allocate_Vector(indices_count);
		s_vector = allocate_Vector(indices_count);
		s = mem_alloc_and_zero(indices_count, sizeof(int));

		/*  Compute the vector "S" */
		for (i = 0; i < indices_count; i++)
			s[i] = (IS_POSITIVE(eigenVector->data[i]) ? 1 : -1);

		/* Improve the division */
		improve_delta = improve_div(Bg, s);

		/*  Compute the vector "S" */
		for (i = 0; i < indices_count; i++)
			s_vector->data[i] = s[i];

		/* Compute the new modularity score */
		modularity_mat_mlpl_by_vector(Bg, s_vector, helper, 1);
		*deltaQue = 0.5 * scalar_mlpl(s_vector, helper);

		if (IS_POSITIVE(*deltaQue))
		{
			int j;

			for (j = 0; j < indices_count; j++)
			{
				if (s[j] == 1)
					itemslist__add_item_to_list(indices[j], &g1List);
				else
					itemslist__add_item_to_list(indices[j], &g2List);
			}
		} /*  if (IS_POSITIVE(deltaQue)) */
		
		mem_free(s);
		free_vector(helper);
		free_vector(s_vector);
	}
	else /*  "IS_POSITIVE(eigenValue)" is false */
	{
		int i;
		for (i = 0; i < indices_count; i++)
			itemslist__add_item_to_list(indices[i], &g1List);
	}/* if (IS_POSITIVE(eigenValue)) */
	
	*g1 = (int*) itemslist__to_array(g1List);
	*g1Count = g1List.count;
	qsort((void*) *g1, (size_t) *g1Count, sizeof(int), compare_unique);

	*g2 = (int*) itemslist__to_array(g2List);
	*g2Count = g2List.count;
	qsort((void*) *g2, (size_t) *g2Count, sizeof(int), compare_unique);


	free_vector(eigenVector);
	free_modularity_mat(Bg);
	itemslist__delete_vector(g1List);
	itemslist__delete_vector(g2List);
}

/*  This function compares unique (guarranteed to not be equal) */
/*  elements */
int compare_unique(const void* arg1, const void* arg2)
{
	int int1 = *(int*) arg1;
	int int2 = *(int*) arg2;

	/*if (int1 == int2)
		return 0;
	else*/ if (int1 > int2)
		return 1;
	else
		return -1;
}

void printGroup(int* g,int size)
{
	int i;

	for (i = 0 ; i < size ; i++)
		printf("%i " , g[i] );

	printf("\n");
}